package Offer;

/**
 *正则表达式匹配
 * 动态规划
 * @author 是阿秋啊
 * @date 2022/08/18 20:23
 **/
public class Num19 {
    public boolean isMatch(String s, String p) {
        int n = s.length() + 1, m = p.length() + 1;
        boolean[][] dp = new boolean[n][m];
        dp[0][0] = true;
        // 处理s为空的情况
        for(int i = 2; i < m; i+=2) {
            //当s为空时，p必须满足a*b*.*这样的结构才能匹配成空串
            //当s不为空，p为空为false
            dp[0][i] = dp[0][i - 2] && p.charAt(i - 1) == '*';
        }
        for(int i = 1; i < n; i++){
            for(int j = 1; j < m; j++){
                if(p.charAt(j - 1) == '*') {
                    // 和*前字母的前一个匹配
                    if(dp[i][j - 2]) dp[i][j] = true;
                        // 和*前的字母匹配
                    else if(dp[i - 1][j] && s.charAt(i - 1) == p.charAt(j - 2)) dp[i][j] = true;
                        // *前为。
                    else if(dp[i - 1][j] && p.charAt(j - 2) == '.') dp[i][j] = true;
                }else {
                    // 不是*号正常匹配，分别为‘.’和相同的情况
                    dp[i][j] = dp[i - 1][j - 1] && (p.charAt(j - 1) == '.' || s.charAt(i - 1) == p.charAt(j - 1));
                }
            }
        }
        return dp[n - 1][m - 1];
    }
}